【题解】 YY的GCD 莫比乌斯反演 luogu2257

又是一道反演题，显然，题目要求我们求出下式：

$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]$

这个不好求，我们来推式子。

设 $n \leq m$

$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]$ $=\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k] \cdot[k \in prime]$ $=\sum_{k=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[gcd(i,j)=1]\cdot[k \in prime]$

我们知道 $\mu$ 函数的一个性质：

$[n=1]=\sum_{d|n} \mu(d)$

将 $n$ 换为 $gcd(i,j)$ ，然后扔回原式。

$[n=1]=\sum_{d|n} \mu(d) \ \Rightarrow \ [gcd(i,j)=1]=\sum_{d|gcd(i,j)} \mu(d)$ $\sum_{k=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|gcd(i,j)}\mu(d) \ \ \ (k \in prime)$ $=\sum_{k=1}^{n}\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[d|gcd(i,j)]\cdot \mu(d) \ \ \ (k \in prime)$ $=\sum_{k=1}^{n}\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor}[1|gcd(i,j)]\cdot \mu(d) \ \ \ (k \in prime)$ $=\sum_{k=1}^{n}\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor}\mu(d) \ \ \ (k \in prime)$

我们知道，这里的 $\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor}$ 可以变成 $\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$ 的，这是等价的。于是：

$=\sum_{k=1}^{n}\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\mu(d)\cdot \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \ \ \ (k \in prime)$

这个式子依旧不可做，因为会超时，考虑如何再一步优化。

设 $T=kd$ ，那么我们枚举 $T$ ：

$=\sum_{T=1}^{n}\sum_{k|T,k\in prime}\mu(\frac{T}{k})\cdot \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$

$QvQ$ 我们将 $\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$ 扔到前面去。

$=\sum_{T=1}^{n}\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor\sum_{k|T,k\in prime}\mu(\frac{T}{k}) $

显然后面的可以预处理，预处理好了后，我们所需要计算的就是这一块：

$\sum_{T=1}^{n}\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor$

这个特别好处理，整除分块优化一波，复杂度 $O(\sqrt(n))$ 。

开始居然感觉这题不可做，然后想要不要用毒教筛来筛 $\mu$ 的前缀和，不过显然我是不会这种黑科技的 $QwQ$

Code：

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=1e7+2;
const int inf=1e9+9;

int vis[N],sum[N],mui[N],f[N],prime[N],cnt;

inline void _pre_mui(){
    mui[1]=1;
    for(int i=2;i<=N;++i){
        if(!vis[i])prime[++cnt]=i,mui[i]=-1;
        for(int j=1;j<=cnt;++j){
            if(i*prime[j]>N)break;
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){mui[i*prime[j]]=0;break;}
            else mui[i*prime[j]]=-mui[i];
        }
    }
    for(int i=1;i<=cnt;++i)
        for(int j=1;prime[i]*j<=N;++j)
            f[j*prime[i]]+=mui[j];
    for(int i=1;i<=N;++i)sum[i]=sum[i-1]+f[i];
    return;
}

inline ll solve(int n,int m){
    ll ans=0;
    for(int l=1,r=0;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=(ll)(sum[r]-sum[l-1])*(ll)(n/l)*(ll)(m/l);
    }return ans;
}

int main(){
    _pre_mui();
    int n,m,T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        if(n>m)std::swap(n,m);
        printf("%lld\n",solve(n,m));
    }return 0;
}

本文标题:【题解】 YY的GCD 莫比乌斯反演 luogu2257

文章作者:Qiuly

发布时间:2019年02月28日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/02/28/[题解]luoguP2257/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。